/* Copyright 2011 Tobias Marschall, Email: tm@cwi.nl 
 * 
 * This file is part of string-cover.
 *
 * string-cover is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * string-cover is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with string-cover.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <vector>
#include <boost/dynamic_bitset.hpp>
#include <string.h>

#include "SubstringStore.h"
#include "StringFactorization.h"

#include "SimpleBoundProvider.h"

using namespace std;

SimpleBoundProvider::SimpleBoundProvider(const Multipliers& multipliers) : multipliers(multipliers) {
}

SimpleBoundProvider::~SimpleBoundProvider() {
}

void SimpleBoundProvider::setMinLength(int min_length) {
	this->min_length = min_length;
}

void SimpleBoundProvider::setMaxLength(int max_length) {
	this->max_length = max_length;
}

std::auto_ptr<Solution> SimpleBoundProvider::compute_bounds(BranchAndBoundNode& node, double global_upper_bound, double* lower_bound, double* substring_weight_sums) const {
	const ProblemInstance& instance = node.getProblemInstance();
	const vector<string>& strings = instance.getStrings();
	const SubstringStore& substrings = instance.getSubstrings();
	if (substring_weight_sums != 0) {
		memset(substring_weight_sums, 0, sizeof(double)*substrings.size());
	}
	auto_ptr<vector<StringFactorization> > factorizations(new vector<StringFactorization>());
	*lower_bound = node.weightOfIncluded();
	boost::dynamic_bitset<> solution_substrings(substrings.size());
#ifdef DEBUG
	cout << "Computing shortest path" << endl;
#endif
	for (size_t string_idx=0; string_idx<strings.size(); ++string_idx) {
		const string& s = strings[string_idx];
		// min_costs[i] is the shortest path length to the point between s[i-1] and s[i]
		double* min_costs = new double[s.size()+1];
		int* back_trace = new int[s.size()+1];
		min_costs[0] = 0.0;
		back_trace[0] = -1;
		for (size_t i=1; i<=s.size(); ++i) {
			min_costs[i] = numeric_limits<double>::infinity();
			back_trace[i] = -1;
			for (size_t j=0; j<i; ++j) {
				// index of substring for edge j->i
				size_t substring_idx = substrings.getIndex(string_idx,j,i);
				int length = i-j;
				if (node.isForbidden(substring_idx)) continue;
				if ((min_length>0) && (length<min_length)) continue;
				if ((max_length>0) && (length>max_length)) continue;
				double edge_weight;
				if (node.isIncluded(substring_idx)) {
					edge_weight = 0.0;
				} else {
					edge_weight = multipliers.get(string_idx, j, i);
				}
				double c = min_costs[j] + edge_weight;
				if (c<min_costs[i]) {
					min_costs[i] = c;
					back_trace[i] = j;
				}
			}
		}
		if (min_costs[s.size()] < numeric_limits<double>::infinity()) {
			*lower_bound += min_costs[s.size()];
		} else {
			return auto_ptr<Solution>(0);
		}
		// use backtrace to obtain factorization
		StringFactorization factorization(s.size());
		int i = s.size();
		while (back_trace[i]>=0) {
			size_t substring_nr = substrings.getIndex(string_idx,back_trace[i],i);
			if (substring_weight_sums != 0) {
				substring_weight_sums[substring_nr] += multipliers.get(string_idx,back_trace[i],i);
				// cout << "BT: " << substrings.getSubstring(substring_nr)<< ": " << multipliers.get(string_idx,back_trace[i],i) << endl;
			}
			solution_substrings.set(substring_nr);
			if (back_trace[i]==0) break;
			i = back_trace[i];
			factorization.addBreakpoint(i-1);
		}
		factorizations->push_back(factorization);
		delete[] back_trace;
		delete[] min_costs;
	}
	if (substring_weight_sums != 0) {
		for (size_t i=0; i<substrings.size(); ++i) {
			substring_weight_sums[i] /= instance.getWeight(i);
		}
	}
#ifdef DEBUG
	cout << "Finished computing shortest path" << endl;
#endif
	double score = 0.0;
	for (size_t i = solution_substrings.find_first(); i!=boost::dynamic_bitset<>::npos; i=solution_substrings.find_next(i)) {
		// cout << substrings.getSubstring(i);
		// if (substring_weight_sums != 0) {
		// 	cout << ": " << substring_weight_sums[i];
		// }
		// cout << endl;
		score += instance.getWeight(i);
	}
	return auto_ptr<Solution>(new Solution(instance,score,factorizations));
}


